package nl.unimaas.games.tron.player;

import java.awt.Color;
import java.lang.reflect.Field;
import java.util.ArrayList;

import org.w3c.dom.NamedNodeMap;

import nl.unimaas.games.tron.engine.Board;
import nl.unimaas.games.tron.engine.Evaluator.SpaceEvaluator;
import nl.unimaas.games.tron.player.MCTSPlayer.Node;
import nl.unimaas.games.tron.player.mcts.CutOffStrategy;
import nl.unimaas.games.tron.player.mcts.FinalNodeSelectionStrategy;
import nl.unimaas.games.tron.player.mcts.PlayoutStrategy;
import nl.unimaas.games.tron.player.mcts.SolverSelectionStrategy;

/** 2-player game */
@SuppressWarnings("serial")
public class MCTSSolverPlayer extends Player {
	protected static boolean DEBUG = false;
	private final static double SIM_WIN = 1, SIM_DRAW = 0, SIM_LOSS = -1;
	protected long MAX_TURN_TIME = 1000;

	private int turn = 0;
	
	protected SolverNode root;
	protected Board rootBoard, currentBoard;
	
	protected boolean applySpaceEstimation;
	protected boolean applyExpansionCutOff = false;
	protected boolean applySimulationCutOff = false;
	private boolean endgame = false;
	
	protected SolverSelectionStrategy select = SolverSelectionStrategy.UCT;
	protected PlayoutStrategy playout = PlayoutStrategy.RANDOM;
	protected FinalNodeSelectionStrategy finalMove = FinalNodeSelectionStrategy.SECURE_SOLVED_CHILD;
	protected CutOffStrategy cutOff = CutOffStrategy.SPACE;
	protected SpaceEvaluator spaceEval = new SpaceEvaluator();
	
	public MCTSSolverPlayer(String name, int num, Color c) {
		super(name, num, c);
	}

	@Override
	protected int computeMove(Board b, long endTime) {
		turn++;
		applySpaceEstimation = (applyExpansionCutOff || applySimulationCutOff);
		try {
			long start = System.currentTimeMillis();
			if (DEBUG)
				System.out.println();

			if (root == null) {//first move of the game 
				turn = 0;
				endgame = false;
				root = createNode(1 - getNumber(), null, Board.MOVE_NONE, b);
				onComputeFirstMove(root);
			}
			rootBoard = b;
			
			if (endTime == 0)
				endTime = System.currentTimeMillis() + MAX_TURN_TIME;
			
			int move = MCTSSolver(root, endTime);
			if (DEBUG) {
				System.out.println("PERFORM MOVE " + Board.moveToString(move) + " (in " + (System.currentTimeMillis() - start) + " ms) at T" + turn);
			}
			return move;
		}
		catch (Exception e) {
			e.printStackTrace();
			System.out.println("error in MCTSSolverPlayer! " + e.getMessage());
			return Board.MOVE_NONE;
		}
	}
	
	@Override
	public synchronized void onPlayerMove(final Board b, int playerNr, int move) {
		if (playerNr == getNumber()) 
			return;
		
		if (root.children.isEmpty())
			throw new IllegalStateException("root has no children");
		for (int i = 0; i < root.children.size(); i++) {
			Node child = root.children.get(i);
			if (child.move == move) {
				child.parent.apply(rootBoard);
				child.parent = null;
				root = (SolverNode) child;
				child.apply(rootBoard);
				if (!rootBoard.equals(b)) {
					rootBoard.print();
					b.print();
					throw new IllegalStateException("boards do not match");
				}
				return;
			}
		}
		throw new IllegalStateException("cannot move to the correct state");
	}
	
	protected int MCTSSolver(SolverNode root, long endTime) {
		//System.out.println("I have " + (endTime - System.currentTimeMillis()) + " ms to compute a result");
		if (endTime - System.currentTimeMillis() < 100)
			System.err.println("MCTS: I have less than 100 ms to compute a result!");
		SolverNode current;
		currentBoard = rootBoard.deepClone(false);
		int its = 0, endIts = 0, cuts = 0;
		double r;
	
		if (root.proven) {
			//System.out.println("endgame!!!!!!!!!! proof");
		}
		
		if (root.prediction != CutOffStrategy.UNDECIDED) {
			endgame = true;
			//System.out.println("endgame!!!!!!!!!! space");
			root.prediction = CutOffStrategy.UNDECIDED;
			root.expanded = false;
		}
		
		if (DEBUG && root.children.isEmpty())
			System.out.println("Root has no children");
		root.proven = false;
		root.prediction = CutOffStrategy.UNDECIDED;
		
		while (System.currentTimeMillis() < endTime && !root.proven) {
			current = root;
			rootBoard.copyTo(currentBoard, false);

			if (root.proven) {
				System.out.println("Not going to bother with this proven root");
				break;
			}
			
			while (!current.isLeaf() && current.expanded) {			
				current = select(current);
				if (current == null)
					break;
			}
			
			if (current == null)
				continue;
			
			//check for a possible game cut off
			r = 0;
			expand(current, currentBoard);

			if (current.children.isEmpty()) {
				// terminal state //
				if (current.prediction == CutOffStrategy.UNDECIDED) {
					//the other player has no more moves
					int myPos = currentBoard.getPlayerPosition(current.playerNr);
					int otherPos = currentBoard.getPlayerPosition(1 - current.playerNr);
					if (myPos == otherPos) {
						r = SIM_DRAW; //crash -> draw
					}
					else {
						//check if we have any moves left
						if (currentBoard.getValidMoveCount(Board.posToX(currentBoard, myPos), Board.posToY(currentBoard, myPos)) == 0)
							r = SIM_DRAW; //both players are stuck -> draw
						else
							r = SIM_WIN; //we can still move -> win
					}
				}
				else {
					if (current.prediction == CutOffStrategy.CURRENT_PLAYER_WON)
						r = SIM_WIN;
					else if (current.prediction == CutOffStrategy.OTHER_PLAYER_WON)
						r = SIM_LOSS;
					else
						r = SIM_DRAW;
				}
					
				double p_r = r;
				if (current.isOpponentNode())
					p_r *= -1;
				
				current.pess = p_r;
				current.opti = p_r;
				current.proven = true;

				propagatePessimisticBound(current);
				propagateOptimisticBound(current);
				//update the 'proven' field
				SolverNode cur = current;
				do {
					if (!cur.checkIfProven())
						break;
					cur = (SolverNode) cur.parent;
				} while (cur != null);
				endIts++;
			}
			else {
				current = select(current);
				if (current == null)
					continue;
				if (current.proven) {
					System.err.println("Prooooven nodeee");
				}
				//simulation starts from one of our moves, player 2 moves first
				r = simulate(current, currentBoard);
				its++;
			}

			/* Backpropagation phase*/
			do {
				current.value += r;
				if (r == 0)
					current.draws++;
				else if (r > 0)
					current.wins++;

				r *= -1;
				current.visits++;
				current = (SolverNode) current.parent;
			} while (current != null);
		}
		
		//System.out.println("Solver Simulations: " + its);
		if (DEBUG) {
			System.out.println("Simulations: " + its + "  Proof passes: " + endIts + " Cuts: " + cuts);
			System.out.println("Root: " + root);
			System.out.println("Root visits: " + root.visits);
			System.out.println("Root children: ");
			root.printChildren();
		}

		for (int i = 0; i < root.children.size(); i++) {
			SolverNode c = (SolverNode) root.children.get(i);
			if (DEBUG && c.proven && c.opti == 1 && c.pess == 1)
				System.err.println("Playing " + Board.moveToString(c.move) + " is a guaranteed win!");
		}
		SolverNode prevRoot = root;
		
		if (root.children.isEmpty())
			System.err.println("Root has no children!");
		
		root = (SolverNode) finalMove.getNode(root);
		
		if (root == null)
			System.err.println("Got null from finalMove.getNode(root)!");
		
		//root.parent.printChildren();
		
		this.root = root;
		if (root.children.isEmpty()) {
			root.expanded = false;
			root.prediction = CutOffStrategy.UNDECIDED;
			root.spaceDiff = Double.NaN;
			root.proven = false;
			rootBoard.copyTo(currentBoard, false);
			root.apply(currentBoard);
			expand(root, currentBoard);
		}
		if (DEBUG && root.proven)
			System.out.println("Root proven!");
		onFinishComputation(root);
		//discard the upper part of the tree
		root.parent = null;
		if (DEBUG)
			System.out.println("Best node: " + root);
		return root.move;
	}
	
	/** Selects a child node of the current node */
	protected SolverNode select(SolverNode node) {
		SolverNode n = (SolverNode) select.getNode(node);
		if (n == null) {
			if (DEBUG && false)
				System.err.println("no non-proven child node to select");
		}
		else
			n.apply(currentBoard);
		return n;
	}
	
	protected void expand(SolverNode node, Board board) {
		if (!node.expanded) {
			//the other player performs a move
			int myNr = 1 - node.playerNr;
			node.expanded = true;
			//pre-create all nodes
			int myPos = board.getPlayerPosition(myNr);
			int myX = Board.posToX(board, myPos), myY = Board.posToY(board, myPos);

			ArrayList<Integer> moves = board.getValidMoves(myX, myY);
			if (!endgame && applyExpansionCutOff 
					&& node.playerNr != getNumber() 
					&& !moves.isEmpty()
					&& !node.isRoot()) {
				node.spaceDiff = spaceEval.compute(board, node.playerNr);
				node.connected = spaceEval.isConnected();
				node.prediction = cutOff.getEnding(node, board);
			}
			
			if (node.prediction == CutOffStrategy.UNDECIDED) {
				for (int m : moves) {
					Node n = createNode(myNr, node, m, board);
					node.children.add(n);
				}
				
				//since we moved first, the current player (2) might be able turn the game into a draw
				if (myNr != getNumber()) {
					int otherNr = node.playerNr;
					int otherPos = board.getPlayerPosition(otherNr);
					int otherX = Board.posToX(board, otherPos), otherY = Board.posToY(board, otherPos);
					if (Board.getManhattanDistance(myX, myY, otherX, otherY) == 1) {
						int m = Board.getMoveFromPositions(myX, myY, otherX, otherY);
						Node n = createNode(myNr, node, m, board);
						n.expanded = true;
						node.children.add(n);
					}
				}
			}
		}
	}
	
	/** Simulates a game from the viewpoint of the player of the given node */
	protected double simulate(final SolverNode node, Board board) {		
		int myMove, otherMove;
		
		int myNr = node.playerNr;
		int myPos = board.getPlayerPosition(myNr);
		int myX = Board.posToX(board, myPos), myY = Board.posToY(board, myPos);
		//get position
		int otherNr = 1 - node.playerNr;
		int otherPos = board.getPlayerPosition(otherNr);
		int otherX = Board.posToX(board, otherPos), otherY = Board.posToY(board, otherPos);

		if (myNr == getNumber()) {
			//player 2 still has to perform a move first
			otherMove = playout.getMove(board, otherX, otherY, otherNr);
			
			if (otherMove == Board.MOVE_NONE) {
				//check if he could've moved to our square, as that would make it a tie since it's his only option
				if (Board.getManhattanDistance(myX, myY, otherX, otherY) == 1)
					return SIM_DRAW;
				else
					return SIM_WIN; //he's stuck
			}

			otherPos = board.getPositionFromMove(otherX, otherY, otherMove);
			if (myPos == otherPos)
				return SIM_DRAW; //tie
			board.performMove(otherX, otherY, otherMove, otherNr, false);
			otherX = Board.posToX(board, otherPos);
			otherY = Board.posToY(board, otherPos);
		}
		
		int it = 0;
		while (true) {
			myMove = playout.getMove(board, myX, myY, myNr);
			otherMove = playout.getMove(board, otherX, otherY, otherNr);
			
			if (myMove == Board.MOVE_NONE) {
				if (otherMove == Board.MOVE_NONE) 
					return SIM_DRAW; //both players did not move
				else
					return SIM_LOSS; //I did not move
			}
			else if (otherMove == Board.MOVE_NONE)
				return SIM_WIN; //other did not move
			
			myPos = board.getPositionFromMove(myX, myY, myMove);
			otherPos = board.getPositionFromMove(otherX, otherY, otherMove);
			
			if (myPos == otherPos)
				return SIM_DRAW;
			
			//perform moves
			board.performMove(myX, myY, myMove, myNr, false);
			board.performMove(otherX, otherY, otherMove, otherNr, false);
			
			//update positions
			myX = Board.posToX(board, myPos);
			myY = Board.posToY(board, myPos);
			otherX = Board.posToX(board, otherPos);
			otherY = Board.posToY(board, otherPos);
			
			it++;
			if (applySimulationCutOff && it % 5 == 0) {
				double diff = spaceEval.compute(board, myNr);
				if (diff != 0 && !Double.isNaN(diff)) {
					return (diff > 0) ? SIM_WIN : SIM_LOSS;
				}
			}
		}
	}
	
	private void propagatePessimisticBound(SolverNode s) {
		if (!s.isRoot()) {
			SolverNode n = (SolverNode) s.parent;
			double oldPess = n.pess;
			if (oldPess < s.pess) {
				if (!n.max) {
					n.pess = s.pess;
					propagatePessimisticBound(n);
				}
				else {
					double minPess = Double.POSITIVE_INFINITY;
					for (int i = 0; i < n.children.size(); i++) {
						SolverNode c = (SolverNode) n.children.get(i);
						if (c.pess < minPess)
							minPess = c.pess;
					}
					n.pess = minPess;
					if (oldPess < n.pess) 
						propagatePessimisticBound(n);
				}
			}
		}
	}
	
	private void propagateOptimisticBound(SolverNode s) {
		if (!s.isRoot()) {
			SolverNode n = (SolverNode) s.parent;
			double oldOpti = n.opti;
			if (oldOpti > s.opti) {
				if (!n.max) {
					double maxOpti = Double.NEGATIVE_INFINITY;
					for (int i = 0; i < n.children.size(); i++) {
						SolverNode c = (SolverNode) n.children.get(i);
						if (c.opti > maxOpti)
							maxOpti = c.opti;
					}
					n.opti = maxOpti;
					if (oldOpti > n.opti)
						propagateOptimisticBound(n);
				}
				else {
					n.opti = s.opti;
					propagateOptimisticBound(n);
				}
			}
		}
	}
	
	protected void onComputeFirstMove(SolverNode theRoot) {}
	
	protected void onFinishComputation(SolverNode newRoot) {}
	
	protected SolverNode createNode(int player, SolverNode parent, int move, Board b) {
		SolverNode n;
		boolean max = (player == getNumber());
		if (parent == null)
			n = new SolverNode(player, max);
		else
			n = new SolverNode(parent, player, move, max);
		return n;
	}
	
	@Override
	public void reset() {
		turn = 0;
		root = null;
	}
	
	public static class SolverNode extends Node {
		public double pess, opti;
		public boolean proven = false;
		
		public boolean isProvenWin() {
			return (proven && pess == 1);
		}
		
		public boolean isProvenDraw() {
			return (proven && pess == 0);
		}
		
		public boolean isProvenLoss() {
			return (proven && opti == -1);
		}
		
		/** @return minimum number of steps needed to win */
		public int getWinSteps() {
			if (!isProvenWin())
				throw new IllegalStateException("win???");
			
			int minSteps = Integer.MAX_VALUE, steps;
			if (children.isEmpty()) {
				minSteps = 0;
			}
			else {
				SolverNode n;
				for (int i = children.size(); --i >= 0;) {
					n = ((SolverNode) children.get(i));
					if (n.isProvenWin()) {
						steps = n.getWinSteps();
						if (steps < minSteps)
							minSteps = steps;
					}
				}
			}
			return minSteps + 1;
		}
		
		public SolverNode(int playerNr, boolean max) {
			super(playerNr, max);
			init();
		}
		
		public SolverNode(SolverNode parent, int playerNr, int move, boolean max) {
			super(parent, playerNr, move, max);
			init();
		}
		
		private void init() {
			pess = -1;
			opti = 1;
		}
		
		public boolean checkIfProven() {
			if (isRoot())
				return false;
			proven = (pess == opti);
			if (!proven) {
				for (int i = 0; i < children.size(); i++)
					if (!((SolverNode) children.get(i)).proven)
						return false;
			}
			proven = true;
			return proven;
		}
		
		@Override
		public String toString() {
			return String.format("node[id=%d, move=%s, player=%d, visits=%d, wins=%.1f%% (%d), draws=%.1f%% (%d), value=%.2f, children=%d, proven=%s (pess=%.0f, opti=%.0f)]", id,  Board.moveToString(move), playerNr, visits, wins / (float) visits * 100, wins, draws / (float) visits * 100, draws, value, children.size(), Boolean.toString(proven), pess, opti);
		}
	}

	public static Player fromXml(org.w3c.dom.Node playerRoot, int num, Color color) {
		return fromXml(playerRoot, new MCTSSolverPlayer(MCTSSolverPlayer.class.getSimpleName(), num, color));
	}
	public static Player fromXml(org.w3c.dom.Node playerRoot, MCTSSolverPlayer player) {
		NamedNodeMap attrs = playerRoot.getAttributes();
		player.description = "";
		if (attrs.getNamedItem("finalMove") != null) {
			try {
				Field field = FinalNodeSelectionStrategy.class.getField(attrs.getNamedItem("finalMove").getNodeValue());
				player.finalMove = (FinalNodeSelectionStrategy) field.get(null);
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		if (attrs.getNamedItem("selection") != null) {
			try {
				Field field = SolverSelectionStrategy.class.getField(attrs.getNamedItem("selection").getNodeValue());
				player.select = (SolverSelectionStrategy) field.get(null);
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		if (attrs.getNamedItem("playout") != null) {
			try {
				Field field = PlayoutStrategy.class.getField(attrs.getNamedItem("playout").getNodeValue());
				player.playout = (PlayoutStrategy) field.get(null);
				player.description += String.format("playout=%s", field.getName());
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		if (attrs.getNamedItem("cut") != null) {
			try {
				String cutType = attrs.getNamedItem("cut").getNodeValue();
				if (cutType.equals("SPACE"))
					player.cutOff = CutOffStrategy.SPACE;
				else
					player.cutOff = null;
			} catch (Exception e) {
				player.cutOff = null;
				e.printStackTrace();
			}
		}
		else
			player.cutOff = null;
		
		if (attrs.getNamedItem("expCut") != null) {
			try {
				player.applyExpansionCutOff = Boolean.parseBoolean(attrs.getNamedItem("expCut").getNodeValue());
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		else
			player.applyExpansionCutOff = false;
		
		if (attrs.getNamedItem("simCut") != null) {
			try {
				player.applySimulationCutOff = Boolean.parseBoolean(attrs.getNamedItem("simCut").getNodeValue());
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		else
			player.applySimulationCutOff = false;

		if (attrs.getNamedItem("maxTurnTime") != null) {
			try {
				player.MAX_TURN_TIME = Long.parseLong(attrs.getNamedItem("maxTurnTime").getNodeValue());
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		player.description = String.format("select=%s playout=%s cut=%s final=%s expCut=" + player.applyExpansionCutOff + " simCut=" + player.applySimulationCutOff, player.select, player.playout, player.cutOff, player.finalMove);
		player.DEBUG = false;
		return player;
	}

	@Override
	public MCTSSolverPlayer clone() {
		MCTSSolverPlayer player = new MCTSSolverPlayer(getName(), getNumber(), getColor());
		player.select = select;
		player.finalMove = finalMove;
		player.cutOff = cutOff;
		player.playout = playout;
		player.description = description;
		player.spaceEval = spaceEval;
		player.applyExpansionCutOff = applyExpansionCutOff;
		player.applySimulationCutOff = applySimulationCutOff;
		player.applySpaceEstimation = applySpaceEstimation;
		//player.DEBUG = true;
		return player;
	}
}